package com.zx._12_算法.左程云算法练习;

import com.zx._12_算法.LinkNode;

/**
 * 单向链表反转
 */
public class Case_07 {

    public static void main(String[] args) {
        LinkNode nodes = LinkNode.getNodes(0, 1, 2, 3, 4);
        nodes.print();

        LinkNode res1 = run2(nodes);
        res1.print();
    }

    /**
     * 1.循环反转
     *
     * @param head
     * @return
     */
    public static LinkNode run1(LinkNode head) {
        LinkNode last = head;
        LinkNode cur = last.next;
        last.next = null;
        LinkNode next = null;
        while (true) {
            // 先提取出下一个
            next = cur.next;
            cur.next = last;
            if (next == null) {
                break;
            } else {
                last = cur;
                cur = next;
            }
        }
        return cur;
    }

    /**
     * 2.递归反转
     *
     * @param head
     * @return
     */
    public static LinkNode run2(LinkNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        LinkNode cur = head;
        LinkNode next = head.next;

        LinkNode zuihouyige = run2(next);

        cur.next = null;
        next.next = cur;

        return zuihouyige;
    }

}
